304. 二维区域和检索 - 矩阵不可变

Similar Question

leading to the advanced question

Solution Tips

方案一: 二维前缀和

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {
    this.sums = new Array(matrix.length + 1).fill(0).map(()=> new Array(matrix[0].length + 1).fill(0))

    for (let row = 0; row < matrix.length; row++) {
		// 利用一维前缀和, 方便理解
        const colSums = new Array(matrix[0].length + 1).fill(0);
        for (let col = 0; col < matrix[0].length; col++) {
            colSums[col + 1] = colSums[col] + matrix[row][col]
			// 等于上面的矩形 + 当前的一维前缀和
            this.sums[row+1][col+1] = this.sums[row][col + 1] + colSums[col + 1]
        }
    }
};

/**
 * @param {number} row1
 * @param {number} col1
 * @param {number} row2
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    const endSums = this.sums[row2 + 1][col2 + 1]
    const leftSums = this.sums[row2 + 1][col1]
    const topSums = this.sums[row1][col2 + 1]
    const dupSums = this.sums[row1][col1]
    return endSums - leftSums - topSums + dupSums
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(left,right)
*/
var obj = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]])
var param_1 = obj.sumRegion(1, 1, 2, 2)
console.log('param_1: ', param_1);
var param_2 = obj.sumRegion(1, 2, 2, 4)
console.log('param_2: ', param_2);

方案二: 一维前缀和

将二维前缀和看做是多个单行的一位前缀和即可